/** -----------------------------------------------------------------
    University of Engineering and Technology

    AI - Assignment 1
    Student: Nguyen Van Bong
    Class: K53CA
    Date: Apr 20, 2011

    Program: nPuzzle
    Desciption: This program uses A-star algorithm to solve nPuzlle problems
        with n: 3,8,15,24,35,48,63, 80,99
        There are three heristic is used in this program. H1,h2,h3 (see its function bellow)
----------------------------------------------------------------------*/

/// This line defines version of the program
// #define DEBUG
#define RELEASE

/// includes necessary libaray
#include <iostream>
#include <fstream>
#include <cmath>
#include <queue>
#include <list>
#include <set>
#include <cstdlib>
using namespace std;

/// Define input, output files ----------------------------------------
#define INFILE "nPuzzle.inp"
#define OUTFILE "nPuzzle.out"

/// Global constant ---------------------------------------------------
#define STEP_COST 1
#define INF 555555555

#define LUCKY_NUMBER 541235797

#define MAX_N 10

#define LIMIT_3 250000
#define LIMIT_4 600000
#define LIMIT_5 1000000

#define ZERO_TOWN 0

// moving directions
#define MAX_DIRECTION 4
const int dx[MAX_DIRECTION] = {1,0,-1,0};
const int dy[MAX_DIRECTION] = {0,1,0,-1};

#define abs(a) (((a)>0)?(a):(-(a)))

/// Data structures definition -----------------------------------------

/**
    State class:
    This implements a state in search space
*/

class State {
public:
    short int town[MAX_N][MAX_N];   // towns' position
    int g,h;

    State ();

    int f() const;
    // overiding overator for using set structure
    bool operator < (const State &other) const;
    bool operator <= (const State &other) const;
    bool operator > (const State &other) const;
    bool operator >= (const State &other) const;
    bool operator == (const State &other) const;
};

/// Global Variable -------------------------------------------------------

int result;
int numberOfState;
int n,hcase;

/// Using set structure to store visited state
set<State> closeNodes;

/// Using priority queue structure to store open nodes
class moref{    // define a class comparator
public:
  moref(){};
  // compare f between two state
  // if they have the same f, we compare h. Because less h means less steps to reach goal
  bool operator() (const State& lhs, const State&rhs) const
  {
     if (lhs.f() == rhs.f()){
         return (lhs.g < rhs.g);
     } else {
        return (lhs.f() > rhs.f());
     }
  }
};
priority_queue<State,vector<State>,moref> openNodes;


State initState;    // the init state
State goalState;    // the goal state
int igoalState [MAX_N*MAX_N][2];    // inversion of goalState

/// Functions declaration -----------------------------------------------------------

/**
    Read in data from the input file
*/
void readData();

/**
    Print out result to the output file
*/
void printOut();

/// Heuristic Functions
int h1(State &nextState);
int h2(State &nextState);
int h3(State &nextState);

/**
    Find the goal state using the h heuristic function
*/
void searching(int (*h)(State&));


/** --------------------------------------------------------------------------
    Main function:
    Main function to execute A-star Algorithm
*/
int main(int argc, char **argv){
    readData();
    switch (hcase){
        case 1: searching(h1); break;
        case 2: searching(h2); break;
        case 3: searching(h3); break;
    }
    printOut();
    return 0;
}
///------------------------------------------------------------------------------

/// Function implementations ----------------------------------------------------

/**
    State Class
    State()
    f()

    Operators to compare two states in search space. These is used to find state
*/
State::State(){
    g = 0;
    h = 0;
}

int State::f() const{
    return g+h;
}

bool State::operator < (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return false;
        else if (this->town[i][j] < other.town[i][j])
            return true;
    }

    return false;
}

bool State::operator > (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return true;
        else if (this->town[i][j] < other.town[i][j])
            return false;
    }

    return false;
}

bool State::operator <= (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return false;
        else if (this->town[i][j] < other.town[i][j])
            return true;
    }

    return true;
}

bool State::operator >= (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return true;
        else if (this->town[i][j] < other.town[i][j])
            return false;
    }

    return true;
}

bool State::operator == (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
        if (this->town[i][j] != other.town[i][j])
            return false;

    return true;
}


/**
    readDate function:
    read in input data from fil
    including: n, h, init state and goal state
*/
void readData(){
    ifstream fin (INFILE);

    // validate input file
    if (fin.fail()){
        cout << "Error input file!" << endl;
        exit(1);
    }

    // read in n,k
    fin >> n >> hcase;

    n = ceil(sqrt(n));  // calculate size of the puzlle

    // Read in init state
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        fin >> initState.town[i][j];
    }

    // Read in goal state
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        fin >> goalState.town[i][j];
        // calculate inversion of goal state for h3 function
        igoalState[goalState.town[i][j]][0] = i;
        igoalState[goalState.town[i][j]][1] = j;
    }

    fin.close();
}
// end

/**
    printOut function:
    print out result to file
*/
void printOut(){
    ofstream fo (OUTFILE);
    fo << result << " " << numberOfState;
    fo.close();
}
// end

/**
    findNumber function:
    find a town in Puzlle
    and return its position
*/
void findNumber(const State &state, int number, int &x, int &y){
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (state.town[i][j] == number){
            x = i;
            y = j;
            return;
        }
    }
}
// end

/**
    inBoud function:
    check if a position is in puzzle
*/
bool inBound(int x, int y){
    if (x<0 || y <0) return false;
    if (x >= n || y>= n) return false;
    return true;
}
// end

/**
    search function:
    using A* algorithm
*/
void searching(int (*h)(State&)){

    State nowState,nextState;
    int zx,zy;  // position of zero town

    // initialize variables
    numberOfState = 0;
    openNodes.push(initState);
    closeNodes.insert(initState);
    closeNodes.clear();

    while (!openNodes.empty()){

        nowState = openNodes.top();
        openNodes.pop();

        // insert nowSatte to closed nodes and check if the nowState is already considered or not
        if (closeNodes.insert(nowState).second == false) continue;

        #ifdef DEBUG
        cout << nowState.f()<<"|" <<nowState.g<<"|"<<nowState.h<< "|" << numberOfState  <<endl;
        #endif

        // check if the goal state is reached or not
        if (nowState == goalState){
            result = nowState.g;
            return;
        } else {
            // in limited search space
            if ((n==3 && numberOfState > LIMIT_3)
                || (n==4 && numberOfState > LIMIT_4)
                || (n> 5 && numberOfState > LIMIT_5)){
                    // searching will be broken because the number of limit state is overed
                    break;
                }
        }

        // find the position of The ZERO TOWN
        findNumber(nowState,ZERO_TOWN,zx,zy);

        // try to move the zero town to 4 directions
        for (int i=0;i<MAX_DIRECTION;i++)
            if (inBound(zx+dx[i],zy+dy[i])){

                // identify the next state
                nextState = nowState;
                nextState.town[zx][zy] = nextState.town[zx+dx[i]][zy+dy[i]];
                nextState.town[zx+dx[i]][zy+dy[i]] = 0;

                // check if the next state is visited or not
                set<State>::iterator ii = closeNodes.find(nextState);
                if (ii == closeNodes.end()){    // if the next state hasn't visited

                    nextState.g = nowState.g + STEP_COST;
                    // calculate the heuristic function in the next state
                    nextState.h = (*h)(nextState);
                    #ifdef DEBUG
                    if (nextState.h < nowState.h-STEP_COST) nextState.h = nowState.h - STEP_COST;
                    #endif


                    // increase number of state generated
                    numberOfState ++;

                    // enqueue the next state
                    openNodes.push(nextState);
                }

            } // end for

    } // end while

    // end lood with no goal state was found
    result = -1;
}
// end searching()

/// Heuristic functions implementation -------------------------------------------

/**
    h1: number of missplaced town
*/
int h1(State &nextState){
    int result = 0;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0 && (nextState.town[i][j] != goalState.town[i][j])){
        result ++;
    }

    return result;
}
// end h1

/**
    h2: mahattan distance of every towns
*/
int h2(State &nextState){
    int result = 0;
    int x,y;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0){
        findNumber(goalState,nextState.town[i][j],x,y);
        result += abs(x-i)+abs(y-j);
    }

    return result;
}
// end h2

/**
    h3: this is sum of:
     + mahattan distances
     + number of moves due to the linear conflict towns in each row or column.
        To clear, every two towns which in the same row or column but in the inverse order
         need 2 addition moves compared to mahattan distance
         Example: 0 1 2    | 0 2 1
                  3 4 5    | 3 4 5
                  6 7 8    | 6 7 8
             1,2 is two conflict towns. As mahattan distance heuristic, we cannot move 2 to 1 and 1 to two.
             We need at least two more moves.
     + the distance from zero to nearest missplaced town (zero distance)
        Because in two above heuristic distace, they dont calculate the move to the nearest missplaced town.
        For exmplae: 0 1 2  | 0 1 2
                     3 4 5  | 3 4 5
                     8 6 7  | 6 7 8
        To move 6,7,8 we need the zero town here, however the distance from zero town to these town is 2.
        So 1 addition move (maybe the move 0 to 3 is needed)
*/
// mahatan distances and linear conflict
int h3(State &nextState){
    int result = 0;

    /// Calculate mahattan distance and zere distance
    int x,y,zx,zy,mindistance = INF;

    findNumber(nextState,0,zx,zy);
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0){
        findNumber(goalState,nextState.town[i][j],x,y);
        result += abs(x-i)+abs(y-j);
        if (( i != x || j!=y) && ((abs(zx-i)+abs(zy-j)) < mindistance)){
            mindistance = (abs(zx-i)+abs(zy-j));
        }
    }


    /// the distance from ZERO_TOWN to the nearest missplaced town
    if (mindistance < INF && mindistance > 0) {
        // minus because the last move may be duplicated in mahattan prediction)
        result += 2* (mindistance - 1);
    }

    /// count the number of linear conflict pairs
    int numberOfPairs = 0;
    int first,second;
    bool rowList[MAX_N*MAX_N] = {false};
    bool colList[MAX_N*MAX_N] = {false};
    rowList[0] = true;
    colList[0] = true;

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            first = nextState.town[i][j];
            // conflict pairs in rows
            if ((!rowList[first]) && (i == igoalState[first][0])){ // in the same row
                for (int k=j+1;k<n;k++){
                    second = nextState.town[i][k];
                    if ((!rowList[second]) && (i == igoalState[second][0])) // the second number in the same row
                    if (igoalState[first][1] > igoalState[second][1]){
                        numberOfPairs ++;   // in crease the number of conflict pairs
                        rowList[first] = true;
                        rowList[second] = true;
                    }
                }
            }

            // conflict pairs in columns
            if ((!colList[first]) && (j == igoalState[first][1])){ // in the same column
                for (int k= i+1;k<n;k++){
                    second = nextState.town[k][j];      // the second number in the same column
                    if ((!colList[second]) && (j == igoalState[second][1])) // the same column
                    if (igoalState[first][0] > igoalState[second][0]){
                        numberOfPairs ++; // in crease the number of conflict pairs
                        colList[first] = true;
                        colList[second] = true;
                    }
                }
            }
        }
    }

    result += 2*numberOfPairs;

    return result;
}
// end h3
